/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (head == NULL || head->next == NULL) {
            return head;
        }
        if (m == n) {
            return head;
        }

        ListNode *cur = head;
        ListNode *pre = NULL;

        for (int i = 0; i < m - 1; ++i) {
            pre = cur;
            cur = cur->next;
        }

        ListNode *t0 = cur;
        ListNode *t1 = cur->next;
        ListNode *t2 = NULL;

        for (int i = 0; i < n - m; ++i) {
            t2 = t1->next;
            t1->next = t0;
            t0 = t1;
            t1 = t2;
        }

        // pre, [cur, t0], t1
        if (pre == NULL) {
            head = t0;
        } else {
            pre->next = t0;
        }
        cur->next = t1;
        return head;
    }
};
